package com.codingvip.backtracking;

public class Cal8Queens {
    public static void main(String[] args) {
        Cal8Queens cal8Queens = new Cal8Queens();
        cal8Queens.cal8queens(0);

    }

    /**
     * 下标表示行，值表示存放在哪一列
     */

    int[] result = new int[8];

    public void cal8queens(int row) {

        if (row == 8) {
            System.out.println("满足条件：");
            printQueens(result);
            return;
        }
        for (int column = 0; column < 8; column++) {
            if (isOK(row, column)) {
                result[row] = column;
                System.out.println("-Begin Nex Row:"+(row+1));
                cal8queens(row + 1);
            }
        }
    }

    private boolean isOK(int row, int column) {
        int leftup = column - 1, rightup = column + 1;
        for (int i = row - 1; i >= 0; --i) {
            // 第i行的column 列有棋子
            if (result[i] == column) {
                return false;
            }
            if (leftup >= 0) {
                // 左上对角线
                if (result[i] == leftup) {
                    return false;
                }
            }
            if (rightup < 8) {
                // 右上对角线
                if (result[i] == rightup) {
                    return false;
                }
            }
            --leftup;
            ++rightup;

        }
        return true;
    }

    private void printQueens(int[] result) {
        for (int row = 0; row < 8; ++row) {
            for (int column = 0; column < 8; column++) {
                if (result[row] == column) {
                    System.out.print("Q ");
                }else{
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

}



